//
// Created by 麻再挺 on 2021/12/16.
//

#include "ol_graph.h"


// 顶点数
const int OL_VEX_NUM = 6;
// 弧数
const int OL_ARC_NUM = 10;
// 有向图, 无向图数组
const int OL_DGN_ARR[] = {
        1, 2,
        2, 3,
        3, 1,
        1, 4,
        4, 3,
        3, 6,
        6, 1,
        4, 6,
        6, 5,
        5, 4
};

// 有向网, 无向网数组, 多了个权值
const int OL_UDGN_ARR[] = {
        1, 2, 5,
        2, 3, 4,
        3, 1, 8,
        1, 4, 7,
        4, 3, 5,
        3, 6, 9,
        6, 1, 3,
        4, 6, 6,
        6, 5, 1,
        5, 4, 5
};

/**
 * 在图中查找元素位置
 * @param g 图
 * @param v 元素值
 * @return
 */
int LocateOLVex(OLGraph *g, VertexType v);

void CreateODG(OLGraph *g) {
    // 赋值图顶点数
    g->vexNum = OL_VEX_NUM;
    // 赋值弧数
    g->arcNum = OL_ARC_NUM;
    // 依次对顶点本身赋值
    for (int i = 0; i < g->vexNum; ++i) {
        g->xList[i].data = i + 1;
        g->xList[i].firstIn = NULL;
        g->xList[i].firstOut = NULL;
    }
    // 构建十字链表
    for (int i = 0; i < g->arcNum; ++i) {
        int v1 = OL_DGN_ARR[2 * i];
        int v2 = OL_DGN_ARR[2 * i + 1];
        //确定v1、v2在数组中的位置下标
        int m = LocateOLVex(g, v1);
        int n = LocateOLVex(g, v2);
        // 建立弧结点
        ArcBox *p = malloc(sizeof(ArcBox));
        // 赋值尾部位置
        p->tailVex = m;
        // 赋值头部位置
        p->headVex = n;
        // 采用头插法插入新的结点
        p->hLink = g->xList[n].firstIn;
        p->tLink = g->xList[m].firstOut;
        g->xList[n].firstIn = g->xList[m].firstOut = p;
    }

}

int LocateOLVex(OLGraph *g, VertexType v) {
    int i = 0;
    //遍历一维数组，找到变量v
    for (; i < g->vexNum; i++) {
        if (g->xList[i].data == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回 -1
    if (i > g->vexNum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}